// https://leetcode-cn.com/problems/sort-list/
// 148. 排序链表
// 给定链表的头节点 head，请将其按升序排列并返回排序后的链表
import { ListNode, array2list, list2array } from '../utils/index.ts';
function sortList(head: ListNode | null): ListNode | null {
    function merge(
        head1: ListNode | null,
        head2: ListNode | null
    ): ListNode | null {
        const dummyHead = new ListNode(0);
        let current = dummyHead;
        while (head1 !== null && head2 !== null) {
            if (head1.val < head2.val) {
                current.next = head1;
                head1 = head1.next;
            } else {
                current.next = head2;
                head2 = head2.next;
            }
            current = current.next;
        }

        current.next = head1 ? head1 : head2;
        return dummyHead.next;
    }

    function toSortList(
        head: ListNode | null,
        tail: ListNode | null
    ): ListNode | null {
        if (head === null) return null;
        if (head.next === tail) {
            head.next = null;
            return head;
        }

        let slow: ListNode | null = head;
        let fast: ListNode | null = head;
        let mid: ListNode | null = head;
        while (fast !== tail) {
            slow = slow && slow.next;
            fast = fast && fast.next;
            if (fast !== tail) {
                fast = fast && fast.next;
            }
        }

        mid = slow;
        return merge(toSortList(head, mid), toSortList(mid, tail));
    }

    debugger;

    return toSortList(head, null);
}

const head = sortList(array2list([5, 4, 2, 1, 3]));
console.log(list2array(head));
